package examination_practice01;

public class DcMaxArray {
    //使用分治法求最大子段和
    public static int DCMaxArr(int[] arr){
        return divideAndConquer(arr,0,arr.length-1);
    }
    private static int divideAndConquer(int[] arr,int start,int end){
        //如果起始位置等于结束位置，说明只有一个元素、
        if (start==end){
            return arr[start]>0?arr[start] : 0;
        }

        //中间位置
        int mid=(start+end)/2;
        //递归求解左半部分的最大子段和
        int leftMax=divideAndConquer(arr,start,mid);

        //递归求解右半部分的最大子段和
        int rightMax=divideAndConquer(arr,mid+1,end);

        //计算跨越中间位置的最大子段和
        int crossingMax=findCrossingMax(arr,start,end,mid);

        return Math.max(Math.max(leftMax,rightMax),crossingMax);
    }
    private static int findCrossingMax(int[] arr,int start,int end,int mid){
        //计算包含中间位置的左侧最大子段和
        int leftMax=Integer.MIN_VALUE;
        int sum=0;
        for (int i=mid;i>=start;i--){
            sum+=arr[i];
            leftMax=Math.max(leftMax,sum);
        }

        //计算右侧的最大子段和
        int rightMax=Integer.MIN_VALUE;
        sum=0;
        for (int i=mid+1;i<=end;i++){
            sum+=arr[i];
            rightMax=Math.max(rightMax,sum);
        }
        return leftMax+rightMax;
    }


}
